1. Field of Invention
The present invention relates generally to the field of computer graphics and pertains more particularly to sort middle, screen space, graphics geometry compression through redundancy elimination.
2. Discussion of the Prior Art
Modern computer systems have become increasingly graphics intensive. Dedicated special purpose memories and hardware have been developed to meet this need. The majority of graphics systems are built to accelerate the standard graphics pipeline. As an example FIG. 1 shows a block diagram of a graphics pipeline 10 having geometry processing 12 and rasterization 14. The pipeline 10 processes a three dimensional (3D) database 16 having geometric objects 18 and textures 20 into a display image 22 which may be shown to the user on a display monitor (not shown). The geometric objects 18 are typically polygons but may also be triangles, lines, and points. These are also known as primitives. For a particular primitive, its vertices or geometrical point locations (px, py, pz) are typically IEEE floating point values. Also, attributes such as colors, normals, and texture coordinates may be specified at each point or for an entire primitive. In binary, the floating point value is made up of one bit for the sign (S), eight bits for the exponent (E or exp), and twenty-three bits for the significand for a total of thirty-two bits. In the case of a triangle, there are three vertices generally having horizontal (x), vertical (y), and depth (z) coordinates in the form of (v0x, v0y, v0z), (v1x, v1y, v1z), and (v2x, v2y, v2z). These primitive vertex data of the geometric objects are sent for geometry processing 12.
During geometry processing 12, this primitive vertex data undergoes modeling transforms, viewing transforms, and viewpoint transforms. The resulting screen space primitives are specified by a number of setup variables. Now one has (v0x, v0y, v0z) in screen space. Setup variables include the starting values and slope of all of the parameters of the primitive. The number, precision, and type of setup variables will vary from application to application. Geometry processing output may include the screen space locations (x and y) of the triangle vertices, the shaded color values (red, green, blue, alpha), the depths (z), the slope of the edges, colors, opacities, and depths across scanlines, triangles, or both. Calculation of the setup variables may be done at the geometry processing stage or at the rasterization stage. This geometry information varies by the rasterization process used and the techniques disclosed below can work with many varieties of rasterization.
Turning now to FIG. 2, a diagram of scan conversion of two triangle types is shown. FIG. 2 is for illustration purposes only as there exist many equivalent methods to rasterize triangles. For both triangle types, edge 1, the longest side, is the primary vertical edge on which scan conversion starts. All scan conversion proceeds in horizontal lines across the triangle as shown. Textures 20 from FIG. 1 may be used as an auxiliary method for looking up a color of a pixel during the scan conversion process. The texture is literally painted onto the polygon by performing an inverse transform lookup from the pixel coordinate, to the polygon coordinate, into the texture space. Finally, the resulting rasterized data is displayed as the display image 22.
In general, the efficient utilization of the special purpose memories and hardware of the graphics system has not been fully considered. As graphics technologies and products become more prevalent in consumer areas, slim profit margins are demanding the utmost efficiencies. Images rendered from a large number of triangles can create a fundamental bottleneck in the system. Approaches to relieve this situation are to either modify the geometry to create fewer triangles or to compress the triangles that are given. While compression has been used to make many technologies possible, such as communications and video technologies, compression has not been used in conventional graphics systems. Compression is necessary to achieve efficiency in database representation to conserve disk storage, system memory, cache memory, and special purpose memories. Additional savings can be achieved by conserving system bus bandwidths, which becomes more critical with unified computer architectures where graphics and system memory are one and the same.
A definite need exists for a system having an ability to meet the efficiency requirements of graphics intensive computer systems. In particular, a need exists for a system which is capable of compressing geometric data in a skillful manner. Ideally, such a system would have a lower cost and a higher productivity than conventional systems. With a system of this type, system performance can be enhanced. A primary purpose of the present invention is to solve this need and provide further, related advantages.
A geometry compression method is disclosed for sort middle, screen space, graphics of the standard graphics pipeline. The pipeline processes a 3D database having geometric objects such as triangles and textures into a display image which may be shown to the user on a display monitor. Lossless compression is achieved through redundancy elimination. Triangles are processed following their transformation to screen space, so that the vertex world 3D locations are determined in their projection to the screen 2D locations. Triangles may also be processed by back projecting the screen space scanlines to test locations against the world space triangles. The general technique is to identify the portions of the data that have little or no effect on the rendered output and remove them during compression. Specific examples disclosed include full packing, constant color, delta coding, edge sharing, slope coding, and color quantization.